import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class NextPermutation {
    public static void main(String[] args) {
        int[] permutation1 = {1,2,3};
        int[] permutation2 = {3,2,1};
        int[] permutation3 = {1,3,2};

        NextPermutation nextPermutation = new NextPermutation();
//        nextPermutation.nextPermutation(permutation1);
//        nextPermutation.nextPermutation(permutation2);
        nextPermutation.nextPermutation(permutation3);

        printArray(permutation1);
        printArray(permutation2);
        printArray(permutation3);
    }

    private static void printArray(int[] permutation) {
        System.out.println("结果："+Arrays.toString(permutation));

    }
    /**
     * 从左往右，查找后一位大于前一位的数的index，此时可以保证index++后的数都为升序，
     * 拿index -1去和index及index++去比较，拿出大于index-1的值，然后换位
     * 随后将index++后的数据进行升序排序
     *
     * 心得：对于有序的序列要注意：可以用双指针法，在不增加空间复杂的的情况，进行反转
     */
    /**
     * @param nums
     * @return
     */
    public void nextPermutation(int[] nums) {
        int i = nums.length -1;

        while(i>0 && nums[i] <= nums[i-1]){
            i--;
        }
        if(i>0){
            int indexBeforeValue = nums[i-1];
            int indexAfter = i + 1;
            while(indexAfter < nums.length && nums[indexAfter] > indexBeforeValue ){
                indexAfter ++;
            }
            nums[i-1] = nums[indexAfter-1];
            nums[indexAfter-1] = indexBeforeValue;
        }
        reverseArray(nums,i, nums.length-1);
    }

    private void reverseArray(int[] nums,int start ,int end) {
        while(start < end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start ++;
            end --;
        }
    }
}